from typing import *
from math import inf


# 总结
# 动态规划
# 向前准备答案
#
class Solution:

    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        n = len(nums)
        g = n // k
        d = dict()
        for i in range(1 << n):
            if i.bit_count() == g:
                mn, mx = 20, 0
                s = set()
                for j in range(n):
                    if (i >> j) & 1 == 1:
                        if nums[j] in s:
                            break
                        s.add(nums[j])
                        mn = min(mn, nums[j])
                        mx = max(mx, nums[j])
                if len(s) == g:
                    d[i] = mx - mn
        f = [inf] * (1 << n)
        f[0] = 0
        for i in range(1 << n):
            if f[i] != inf:
                s = set()
                sub = 0
                for j in range(n):
                    if (i >> j) & 1 == 0 and nums[j] not in s:
                        sub |= 1 << j
                        s.add(nums[j])
                if sub.bit_count() >= g:
                    enum = sub
                    while enum > 0:
                        if enum in d:
                            f[i | enum] = min(f[i | enum], f[i] + d[enum])
                        enum = (enum - 1) & sub
        return f[(1 << n) - 1] if f[(1 << n) - 1] != inf else -1
